fun find (str, substr) =
	if String.isSubstring substr str = false then 0
	else if String.isPrefix substr str then 1
		else 1 + find(String.extract(str,1,NONE), substr);
        
fun find_all(str, substr) = 
let 
	val first = find(str, substr)
    val offset = if (first + size(substr) - 1 <= 0) then 1
		    	 else first + size(substr) - 1
    fun map f [] = []
    	| map f (x::xs) = (f x) :: map f xs
    val addOffset = map(fn a => a + offset)
in
    if first > 0 then 
    	first::addOffset  
        	(find_all(String.extract(str, offset, NONE), substr)) 
    else []
end

fun replace(str, old, new, n) = 
let
	val occ = find_all(str, old);
in
	if List.length(occ) < n orelse n < 1 then str
    else String.substring(str,0,List.nth(occ,n-1) - 1) ^
    	new ^ 
    	String.extract(str, List.nth(occ,n-1) - 1 + size(old), NONE)
end 

fun replaceAll(str, old, new) = 
let 
	val first = find(str, old)
   	val offset = if (first + size(old) - 1 <= 0) then 1
		    	 else first + size(old) - 1
in
	if first > 0 andalso size(old) > 0 then
   		String.substring(str,0,first - 1) ^ 
       		new ^ 
           	replaceAll(String.extract(str, offset, NONE), old, new) 
   	else str
end


fun zip (x::xs,y::ys) = (x,y)::zip(xs,ys) 
	|	zip (_,_) = [];
    
fun zip_with_index (xs) =
let
	fun upto(m,n) =
    	if m>n then [] else m :: upto(m+1,n)
in
	zip(xs,upto(1,List.length(xs)))
end


fun unzip (xs) = 
	if List.length(xs) <= 0 then ([],[])
    else
    let
    	val (first,second) = unzip(tl xs)
        val (a,b) = hd xs
    in
    	(a::first,b::second)
    end

fun recognizeDFA (dfa,str) = 
let
	fun runDFA(from, dfa:(char -> int) list * int list, str) = 
    	if size(str) = 0 orelse from < 1 then from else 
        	runDFA(List.nth(#1(dfa),from - 1) (String.sub(str,0)), 
            	dfa, String.extract(str, 1, NONE))
    fun isElementOf(element, x::xs) = element = x orelse isElementOf(element, xs)
    	| isElementOf(element, _) = false
in
	isElementOf(runDFA(1, dfa, str), #2(dfa))
end


fun recognizeNFA (nfa,str) = 
let
    fun isElementOf(element, x::xs) = element = x orelse isElementOf(element, xs)
    	| isElementOf(element, _) = false
        
    fun intersect(x::xs, ys) = isElementOf(x, ys) orelse intersect(xs,ys) 
    	| intersect(_, ys) = false
        
	fun merge (x::xs,ys) = if isElementOf(x, ys) then merge(xs,ys) else x::merge(xs,ys)
    	| merge(_,ys) = ys
         
	fun doStep (from, nfa:(char -> int list) list * int list, str) = 
    	if size(str) = 0 orelse List.length(from) = 0 then from else
        	merge(
            	List.nth(#1(nfa),hd(from) - 1) (String.sub(str,0)) ,
            	doStep(tl(from),nfa, str)
                )
    
    fun runNFA (from, nfa, str) = 
    	if size(str) = 0 then from else
    		runNFA(doStep(from, nfa, str), nfa, String.extract(str,1,NONE))
    

in
	intersect(runNFA([1],nfa,str), #2(nfa))
end


fun NFA2DFA(nfa:(char -> int list) list * int list) = 
let
    fun isElementOf(element, x::xs) = element = x orelse isElementOf(element, xs)
    	| isElementOf(element, _) = false
        
    fun intersect(x::xs, ys) = isElementOf(x, ys) orelse intersect(xs,ys) 
    	| intersect(_, ys) = false
        
	fun merge (x::xs,ys) = if isElementOf(x, ys) then merge(xs,ys) else x::merge(xs,ys)
    	| merge(_,ys) = ys 
	
    fun pow (x,0) = 1 
    	| pow (x,y) = x * pow(x, y-1)
    
    (* converts an nfa state to a dfa state *)    
    fun listToInt (x::xs) = pow(2,x-1) + listToInt(xs)
    	| listToInt (_) = 0
        
    (* converts a dfa state to an nfa state (use with k = 1)*) 
    fun intToList (k,0) = []
    	| intToList (k,n) = if n mod 2 = 1 then k::intToList(k+1, n div 2) 
        						else intToList(k+1, n div 2)
    
    (* get the n'th transition function of the desired DFA*)    
    fun getTransition (nfa:(char -> int list) list * int list, state::xs) =
    	(fn (c) => merge(getTransition(nfa, xs) (c), (List.nth(#1(nfa), state - 1)) (c)))
		| getTransition (nfa, xs) = fn (c) => []
        
    fun getTransitionWrapper (nfa:(char -> int list) list * int list, state) = 
    	fn (c) => listToInt((getTransition(nfa, intToList(1,state)) (c)))
        
    fun getTransitionList (nfa:(char -> int list) list * int list, k, n) = if k > n then [] else
		getTransitionWrapper(nfa, k)::getTransitionList (nfa, k+1,n)
    
    fun getAcceptingStates(nfa:(char -> int list) list * int list,k,n) = if k > n then [] else
    	if intersect(intToList(1, k), #2(nfa)) then k::getAcceptingStates(nfa , k + 1, n) else
        	getAcceptingStates(nfa ,k + 1, n)
        	
in
	(getTransitionList(nfa, 1, pow(2, List.length(#1(nfa))) - 1),
     getAcceptingStates(nfa, 1, pow(2, List.length(#1(nfa))) - 1) )
end
	 